home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / ndx300.zip / NDX300.TXT < prev    next >
Text File  |  1992-11-02  |  8KB  |  211 lines
  1.                  NDX -- BTREE INDEXING ROUTINES
  2.                                 
  3.                           Version 3.00
  4.                                 
  5.  Copyright 1987,88,89,92 by George H. Mealy, all rights reserved
  6.                                 
  7.                                 
  8.                                 
  9. INTRODUCTION
  10.  
  11. This package implements yet another variant of the balanced tree
  12. indexing method (Btree) described in section 6.2.4 of D. E.
  13. Knuth's "Sorting and Searching", volume 3 of "The Art of
  14. Programming."  Its features are:
  15.           
  16.           1.  Files with variable length records can be
  17.               indexed.  Data file format is arbitrary,
  18.               since an index is stored as a separate
  19.               file.
  20.          
  21.          2.   Keys are variable length ASCIZ strings.
  22.              The package allows retrieval on heads of
  23.              index keys: when retrieving on the search
  24.              key "FOO", records with keys "FOO",
  25.              "FOO1", "FOOP" and "FOOPU" may be
  26.              retrieved in that order.  That is, a
  27.              search key may be matched by any key of
  28.              which it is a head.  Matching can be case-
  29.              sensitive or case-insensitive.  Search
  30.              behaviour is specified when the index is
  31.              opened.
  32.           
  33.           3.  ISAM access to index entries is avail
  34.               able; it may be first-in-first-out or
  35.               last-in-last-out, as specified when the
  36.               index file is created.
  37.           
  38.           4.  Index file records are cached.  A single
  39.               cache is used when more than one index
  40.               file is open.
  41.           
  42.           5.  The source file is supplied.  The package
  43.               can be compiled using Turbo C version
  44.               1.5+ or Microsoft C version 5.0+.
  45.  
  46. This package is copyrighted material.  You may use it for
  47. noncommercial purposes and make exact and complete copies for
  48. others at cost.  Modified versions of the package may NOT be
  49. copied without express permission.  In any case, no warranty of
  50. any kind is made or implied by the author.
  51.  
  52. The author may be reached at (617) 545-1727.
  53.  
  54.  
  55. INDEX FILE FORMAT
  56.  
  57. The index file begins with a short header, padded with enough
  58. bytes to fill a 512 byte disk sector.  (See NDX.H for the format
  59. of the header and other data structures.)  Nodes in the tree are
  60. 1024 bytes in length on the disk.  Each starts with a value --
  61. that of the node if it is currently in use, or that of the next
  62. node in the chain of free nodes on the disk.  The number of bytes
  63. occupied by keys in the node follows, and then the keys.
  64.  
  65. Each KEY has three fields.  First is the value, if not zero, of a
  66. lower level node which has keys less than or equal to the current
  67. key, followed by a reference to the place in the data file
  68. corresponding to the current key.  Finally, the ASCIZ key itself
  69. is stored.  Please note that only as many bytes as are necessary
  70. are stored.
  71.  
  72. Immediately following the last key in the node, a pointer to the
  73. next lower level may be stored; the field end_keys of NODE does
  74. not include the length of this pointer.
  75.  
  76. The index structure INDEX is allocated and initialized when the
  77. index file is opened.  It contains:
  78.           
  79.           1.  A copy of the file header
  80.           
  81.           2.  A KEY structure which holds the key
  82.               resulting from index file operations.
  83.           
  84.           3.  A stack holding the path from the root of
  85.               the index to the current key entry.
  86.           
  87.           4.  The index file name and handle.
  88.           
  89.           5.  The string comparison function to be used
  90.               during key retrieval.
  91.  
  92.  
  93. USAGE
  94.  
  95.     The constructor
  96.  
  97.     Index::Index(char *indexname, unsigned mode, CFN compfn)
  98.  
  99. creates an empty index file.  The comparison function, if NULL,
  100. defaults to strcmp.  The mode is one of:
  101.           
  102.           NODUPS    No duplicate keys allowed
  103.           
  104.           FIFO           Duplicate keys are retrieved
  105.               first-in-first-out.
  106.           
  107.           LIFO           Duplicate keys are retrieved
  108.               last-in-last out.
  109.  
  110. The mode is stored in the index file header.  A NULL second
  111. argument defaults to NODUPS.  The third argument is the routine
  112. to be used for key matching -- if NULL, strcmp is used.
  113.  
  114.      Index::Index(char *indexname, int (*compfn)())
  115.  
  116. is used to open an existing index file, while the destructor
  117. closes an index file.
  118.  
  119.  
  120.      DWORD Index::insert(char *key, DWORD value);
  121.  
  122. adds a key to the index, except when the mode is NODUPS and the
  123. key is already present.  In this case, the value specified in the
  124. call replaces the previous value.  If successful, insert returns
  125. the specified DWORD and otherwise it returns zero.
  126.  
  127. The value can be a long unsigned seek address used to reference
  128. the data file, or just a serial record number when the data file
  129. has fixed length records.  A valid value may not be zero.  The
  130. comparison function used for insertion is always strcmp.
  131.  
  132.  
  133.      Index::remove(char *key, DWORD value);
  134.  
  135. deletes the key from the index.  If this leaves an empty node,
  136. the node is placed in the freelist.  The second argument is
  137. required due to the possibility of multiple occurrences of the
  138. same key.  Returns 0 for failure and 1 for success.
  139.  
  140.  
  141.      DWORD Index::find(char *key);
  142.  
  143. attempts to find the specified key, according to the comparison
  144. function specified when the file was opened and the mode speci
  145. fied when the file was created.  The value part of the key found
  146. is returned on success; zero is returned on failure.
  147.  
  148. In order to find all occurences of a key when FIFO or LIFO
  149. operation is in effect, use Index::find with a NULL second
  150. argument after the first occurence has been found.
  151.  
  152.  
  153.      DWORD Index::first(unsigned last);
  154.  
  155. positions the index file pointer to the first (last) key in the
  156. index.  The "file pointer" is, strictly speaking, the top stack
  157. entry and contains the seek address of the node and the offset of
  158. the key in that node.  The remainder of the stack records
  159. information required for traveling over the index tree starting
  160. from the file pointer, as if the index were flat rather than a
  161. tree.  Zero is returned if the index is empty, else the value
  162. part of the key located is returned.
  163.  
  164.  
  165.      DWORD Index::next();
  166.      DWORD Index::prev();
  167.  
  168. These routines change the file pointer to the next or previous
  169. key and return the value part of that key, or zero if the current
  170. file pointer was at the end or beginning of the index.
  171.  
  172. Note that Index::find, Index::insert and Index::remove position
  173. the file pointer.  In the latter case, the file pointer is set to
  174. the key following the deleted key.  Note further that each
  175. successful key retrieval stores a copy of the current key
  176. structure in the index structure.
  177.  
  178. For examples of the use of the routines, see the test program.
  179.  
  180.  
  181. IMPROVEMENTS
  182.  
  183. Knuth suggests ways in which the Btree algorithms may be
  184. improved.  If you decide to experiment, be prepared for an
  185. interesting [sic] experience.  Be particularly wary of any
  186. changes you attempt to make in xdelete -- updating the index to
  187. properly reflect a deletion is an extremely tricky affair.  Even
  188. xnext and xprev, which look deceptively simple, are easy to upset
  189. if you try to change the order in which things are done.
  190.  
  191.  
  192. CHANGES
  193.  
  194. My address is:
  195.  
  196.                     George H. Mealy
  197.                     38 Gilson Road
  198.                     Scituate, MA 02066
  199.                     USA
  200.           
  201.                     (617) 545-1727
  202.  
  203. Version 2.02 corrected an egregious blunder in the Index::insert
  204. routine, thanks to John A. Matzen.  I also fixed a bug in
  205. Index::find, thanks to strong type checking and use of the
  206. typedef CFN.  The package has been recompiled using Borland C++
  207. v3.0.
  208.  
  209. The file NDX.DOC is a Word for Windows document.
  210.  
  211.